import java.util.*;

public class Leetcode1604 {
    public static void main(String[] args) {
//        System.out.println(alertNames(new String[]{"daniel", "daniel", "daniel", "luis", "luis", "luis", "luis"}, new String[]{"10:00", "10:40", "11:00", "09:00", "11:00", "13:00", "15:00"}));
//        System.out.println(alertNames(new String[]{"john","john","john"}, new String[]{"23:58","23:59","00:01"}));
        System.out.println(alertNames(new String[]{"leslie", "leslie", "leslie", "clare", "clare", "clare", "clare"}, new String[]{"13:00", "13:20", "14:00", "18:00", "18:51", "19:30", "19:49"}));
        System.out.println(alertNames(new String[]{"a", "a", "a", "a", "a", "b", "b", "b", "b", "b", "b"}, new String[]{"04:48", "23:53", "06:36", "07:45", "12:16", "00:52", "10:59", "17:16", "00:36", "01:26", "22:42"}));
    }

    public static List<String> alertNames(String[] keyName, String[] keyTime) {
        List<String> ans = new ArrayList<>();
        Map<String, PriorityQueue<Integer>> flags = new HashMap<>();
        for (int i = 0; i < keyName.length; i++) {
            PriorityQueue<Integer> flag = flags.getOrDefault(keyName[i], new PriorityQueue<>());
            //这里不用split会快30ms
            flag.add((keyTime[i].charAt(0) - '0') * 600 + (keyTime[i].charAt(1) - '0') * 60 +
                    (keyTime[i].charAt(3) - '0') * 10 + (keyTime[i].charAt(4) - '0'));
            if (flag.size() == 1) {
                flags.put(keyName[i], flag);
            }
        }

        for (Map.Entry<String, PriorityQueue<Integer>> entry : flags.entrySet()) {
            PriorityQueue<Integer> queue = entry.getValue();
            while (queue.size() > 2) {
                int t1 = queue.poll();
                int t2 = queue.peek();
                if (t2 - t1 <= 60) {
                    t2 = queue.poll();
                    int t3 = queue.peek();
                    if (t3 - t1 <= 60) {
                        ans.add(entry.getKey());
                        break;
                    }
                    //记得把第二个加回去，下次还得比第二个
                    queue.offer(t2);
                }
            }
        }

        Collections.sort(ans);
        return ans;
    }
}
